#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <fstream>

using namespace std;

void permute(const string& pre, const string& pos){
	if(pos.size() == 0){
		cout << pre << endl;
		return;
	}
	for(size_t i = 0; i < pos.size(); ++i){
		string a = pre;
		string b = pos;
		char* c = new char(b[i]);
		permute(a.append(c), b.erase(i,1));
	}
}

void permute(const string& str){
	permute("", str);
}

class Coor{
	int rPos, cPos;
public:
	Coor(int r = 0, int c = 0) : rPos(r), cPos(c) {}

	Coor left()const{
		return Coor(rPos, (cPos-1));
	}
	Coor right()const{
		return Coor(rPos, (cPos+1));
	}
	Coor up()const{
		return Coor((rPos-1), cPos);
	}
	Coor down()const{
		return Coor((rPos+1), cPos);
	}

	int r() const {
		return rPos;
	}
	int c() const {
		return cPos;
	}

	friend ostream& operator<<(ostream& os, const Coor& c);
};

ostream& operator<<(ostream& os, const Coor& c){
	//os << "(" << c.rPos << ", " <<  c.cPos << ")";
	os << "Row: " << c.rPos+1 << ", Col: " << c.cPos+1;
	return os;
}

class Maze{
	vector< vector<char> > utility; // this is an array that can be destructively searched
	vector< vector<char> > data;
	int rows, cols;
	Coor start;
public:
	Maze() : rows(0), cols(0) {}
	
	//helpers
	
	int getRows() const{
		return rows;
	}

	int getCols() const{
		return cols;
	}

	bool isValid(const Coor& coor){
		return coor.r() >= 0 && coor.c() >= 0 && coor.r() < rows && coor.c() < cols && (utility[coor.r()][coor.c()]=='.' || utility[coor.r()][coor.c()]=='e');
	}

	//Finders
	Coor recursiveFind(Coor pos){
		//if pos is end return pos
		if(utility[pos.r()][pos.c()]=='e'){
			return pos;
		}
		
		//mark the spot so that we don't look at it any more
		utility[pos.r()][pos.c()] = '0';

		//try all the surroundings (recursion)
		//create the four pos's
		vector<Coor> dirs;
		dirs.push_back( (pos.left())	);
		dirs.push_back( (pos.right())	);
		dirs.push_back( (pos.up())	);
		dirs.push_back( (pos.down())	);
		//check that they are a valid path
		
		for(Coor c : dirs){
			if(isValid(c)){
				Coor endPossibility = recursiveFind(c);
				if(isValid(endPossibility)){	//if endPossibility is NOT the real end it will be equal to -1, -1
					return endPossibility;
				}
			}
		}
		//if all else fails we have hit a dead end
		//return -1 -1
		return Coor(-1, -1);
	}
	Coor recursiveFind(){
		utility = data;
		return recursiveFind(start);
	}

	bool gotOptions(const Coor& coor){
		return isValid(coor.left()) || isValid(coor.right()) || isValid(coor.up()) || isValid(coor.down());
	}

	Coor getAnOption(const Coor& coor){
		if(isValid(coor.left()))
			return coor.left();
		if(isValid(coor.right()))
			return coor.right();
		if(isValid(coor.up()))
			return coor.up();
		if(isValid(coor.down()))
			return coor.down();
		throw "A tantrum";		//this shouldn't actually happen because only the stackFind() uses this
	}

	Coor stackFind(){
		utility = data; //restets the utility array to the clean input
		vector<Coor> posits = {start};
		while(true){
			if(utility[posits.back().r()][posits.back().c()] == 'e'){
				return posits.back();
			}
			utility[posits.back().r()][posits.back().c()] = '0';

			if(gotOptions(posits.back())){
				posits.push_back(getAnOption(posits.back()));
			}
			else{
				posits.pop_back();
			}
		}
	}

	void queueFind(){

	}

	//IO operators
	friend istream& operator>>(istream&, Maze&);
	friend ostream& operator<<(ostream&, const Maze&);
};

istream& operator>>(istream& is, Maze& m){
	char c;
	c= is.get();
	vector<char> v;
	m.data.push_back(v);
	while(c != EOF){//there is no specified end-point really... I'm just gonna conform to standards.
		if(c == '\n'){
			vector<char> v;
			m.data.push_back(v);
		}
		else{
			m.data.back().push_back(c);
		}
		c = is.get();
	}
	
	if(m.data.back().size() == 0){
		m.data.pop_back(); //there is one extra newlin in the input data so I have to pop this off
	}

	m.rows = m.data.size();
	m.cols = m.data[0].size();

	for(int r = 0; r < m.rows; ++r){
		for(int c = 0; c < m.cols; ++c){
			if(m.data[r][c] == 's'){
				Coor coor(r, c);
				m.start = coor;
				return is; 	//we're done this is an easy break out option
			}
		}
	}

	return is;	//because I am superstitious.
}

ostream& operator<<(ostream& os, const Maze& m){
	for(int r = 0; r < m.getRows(); ++r){
		for(int c = 0; c < m.getCols(); ++c){
			os << m.data.at(r).at(c);
		}
		os << endl;
	}
	return os;
}

int main(){
	Maze maize;
	fstream fin("input");
	if(!fin){
		return -555;
	}
	fin >> maize;
	cout << maize << endl << maize.stackFind() << endl << maize.recursiveFind() << endl;
}
